Digital image processing refers generally to methods of performing various tasks upon images stored in digital form. A familiar example of digital image processing is the restoration improvement of photographs or other images taken by satellites or astronauts in outer space and then transmitted to Earth. In simple terms, digital images may be thought of as an array of dots (commonly referred to as "pixels"), with each pixel being assigned a value in accordance with its brightness or luminance. For color images, one pixel may be assigned a value for each primary color of the system. The pixel array may be viewed mathematically as a matrix of data for purposes of digital image processing.
As noted above, digital image processing encompasses restoration, or enhancement either by "smoothing" or "sharpening," and numerous other techniques well known in the art. Each of these techniques is accomplished by some kind of linear convolutional processing or filtering, whether it be convolution, recursive filtering, or Fourier transform filtering. These techniques generally employ two-dimensional filters having finite impulse response (FIR).
Unfortunately, while applications of two-dimensional filtering are becoming of increasing importance, as, for example, in geophysical exploration, earthquake/nuclear test detection, sonar, radar and radio astronomy, in addition to picture encoding, filtering of large size data sets requires a great amount of computation using conventional filtering methods. An example of the computational problems encountered with conventional convolution or filtering techniques can be seen from Digital Image Processing, by William K. Pratt, Wiley-Interscience, 1978, Library of Congress catalog no. TA 1632.P7 1978, particularly chapters 1 and 9. In discrete convolution a filter is defined by an impulse response, or operator, which generally comprises a plurality of values, or parameters, arranged in matrix form. The operator matrix may be viewed as a mask which is then scanned over, or convolved with a generally larger pixel matrix to achieve the desired processing. Typical dimensions of the impulse response array are on the order of 15.times.15 or 21.times.21, but may be as large as 61.times.61. The pixel matrix typically has dimensions on the order of 512.times.512. Thus a single discrete convolution involves approximately 15.multidot.15.multidot.512.multidot.512=58,982,400 computations. It can thus be seen that a more manageable method of digitally processing an image has been required.
There have been some background investigations into more efficient convolution processing methods. In an article by J. H. MacClellan entitled "The Design of Two-Dimensional Digital Filters by Transformations", Proc. 7th Annual Princeton Conf. Information Sciences and Systems, pp. 247-251 (1973), it was shown that a one-dimensional zero-phase FIR filter could be mapped into a two-dimensional zero-phase FIR filter by substitution of variables. In a subsequent article by Mecklenbrauker and Mersereau entitled "MacClellan Transformations for Two-Dimensional Digital Filtering: I-Design, II-Implementation," IEEE Transactions on Circuits and Systems--Vol. CAS-23, No. 7, pp. 405-422 (July 1976), the MacClellan model was generalized and methods were developed to implement such filters by ordinary sequential filtering techniques. A third and fourth section of the article by Mecklenbrauker and Mersereau provided algorithms for determining parameters, and also examples.